package demogo

type BinaryTree struct {
	val   int
	left  *BinaryTree
	right *BinaryTree
}

// 先root 再left 然后right
func preOrderTree(root *BinaryTree) []int {
	if root == nil {
		return nil
	}
	if root.left == nil && root.right == nil {
		return []int{root.val}
	}
	var rest []int
	rest = append(rest, root.val)
	if root.left != nil {
		rest = append(rest, preOrderTree(root.left)...)
	}
	if root.right != nil {
		rest = append(rest, preOrderTree(root.right)...)
	}
	return rest
}

func inOrderTree(root *BinaryTree) []int {
	if root == nil {
		return nil
	}
	if root.left == nil && root.right == nil {
		return []int{root.val}
	}
	var rest []int
	if root.left != nil {
		rest = append(rest, inOrderTree(root.left)...)
	}
	rest = append(rest, root.val)
	if root.right != nil {
		rest = append(rest, inOrderTree(root.right)...)
	}
	return rest
}

func lastOrderTree(root *BinaryTree) []int {
	if root == nil {
		return nil
	}
	if root.left == nil && root.right == nil {
		return []int{root.val}
	}
	var rest []int
	if root.left != nil {
		rest = append(rest, lastOrderTree(root.left)...)
	}
	if root.right != nil {
		rest = append(rest, lastOrderTree(root.right)...)
	}
	rest = append(rest, root.val)
	return rest
}
